//反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 
//
// 说明: 
//1 ≤ m ≤ n ≤ 链表长度。 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL, m = 2, n = 4
//输出: 1->4->3->2->5->NULL 
// Related Topics 链表 
// 👍 447 👎 0

package leetcode.editor.cn;

import java.util.List;

//Java：反转链表 II
public class P92ReverseLinkedListIi {
    public static void main(String[] args) {
        Solution solution = new P92ReverseLinkedListIi().new Solution();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=null;

        ListNode res=solution.reverseBetween(node1,2,4);
        while (res!=null){
            System.out.print(res.val+ " ");
            res=res.next;
        }

        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution {
        /*
        * 这个代码虽然可以AC过 但是在面试中需要考虑的条件太多，容易出错
        * */
        public ListNode reverseBetween1(ListNode head, int m, int n) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode dumpty = new ListNode(0);
            dumpty.next=head;

            //记录反转的前一个指针
            ListNode node = dumpty;

            //用于反转
            ListNode pre = head;
            ListNode curr = head.next;
            ListNode next = null;

            //先走到m处
            int index = 1;
            while (index < m && curr != null) {
                node = node.next;
                pre = pre.next;
                curr = curr.next;
                index++;
            }

            //记录头一个节点，因为一会儿要将它作为末尾
            ListNode tmp = pre;

            //对m到n的节点进行反转
            while (index < n && curr != null) {
                next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
                index++;
            }

            //此时pre为反转后的头结点
            node.next = pre;
            //tmp记录的原来的头结点现在作为尾结点，尾结点指向最后的节点
            tmp.next = curr;

            //返回结果
            return dumpty.next;
        }

        /*
        *  与k个一组翻转链表相似
        *  记录需要翻转的开始节点和结束节点，对该部分进行翻转
        * */
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null || head.next == null) {
                return head;
            }

            ListNode dumpty=new ListNode(0);
            dumpty.next=head;
            ListNode beginNode=dumpty;
            ListNode endNode=dumpty;
            for(int i=1;i<m;i++){//找到其前一个节点
                beginNode=beginNode.next;
            }

            for(int j=0;j<n;j++){//找到最后一个
                endNode=endNode.next;
            }

            ListNode beginNext=beginNode.next;
            ListNode endNext=endNode.next;
            endNode.next=null;
            beginNode.next=reverse(beginNode.next);
            beginNext.next=endNext;
            return dumpty.next;
        }
        public ListNode reverse(ListNode head){
            if(head==null||head.next==null){
                return head;
            }
            ListNode pre=null;
            ListNode curr=head;
            ListNode next=null;

            while (curr!=null){
                next=curr.next;
                curr.next=pre;
                pre=curr;
                curr=next;
            }
            return pre;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
